package com.platform.modules.alg.alglib.poj1703;

public class Poj1703 {
    public String output = "";
    private final int MAXN = 200010; // 因为有影子数据量*2，不然会越界！！run time error！！！

    private int n;
    private int m;
    private int fa[] = new int[MAXN];
    private int h[] = new int[MAXN]; // h 用来区分树的高度，但其不存储树的具体高度

    void Init() {
        for (int i = 1; i <= 2 * n; i++) {
            fa[i] = i;
            h[i] = 0;
        }
    }

    int Find(int x) {
        if (x != fa[x])
            fa[x] = Find(fa[x]);
        return fa[x];
    }

    void Union(int x, int y) {
        int a = Find(x);
        int b = Find(y);
        if (a == b) return;
        if (h[a] > h[b]) //启发式合并，把矮树合并到高树之下
            fa[b] = a;
        else {
            fa[a] = b;
            if (h[a] == h[b])//若树的高度一样，合并后树根的树高+1
                h[b]++;
        }
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        n = Integer.parseInt(words[0]);
        m = Integer.parseInt(words[1]);
        Init();
        for (int i = 0; i < m; i++) {
            String[] word = line[1 + i].split(" ");
            char ch[] = new char[2];
            ch[0] = word[0].charAt(0);
            int x = Integer.parseInt(word[1]);
            int y = Integer.parseInt(word[2]);
            if (ch[0] == 'D') {
                Union(x, y + n);
                Union(x + n, y);
            } else {
                if (Find(y + n) == Find(x) || Find(x + n) == Find(y))
                    output += "In different gangs.\n";
                else if (Find(x) == Find(y) || Find(x + n) == Find(y + n))
                    output += "In the same gang.\n";
                else
                    output += "Not sure yet.\n";
            }
        }
        return output;
    }
}
